package datastructure.book.tujiesuanfa.backtrack._2_more;

import datastructure.book.tujiesuanfa.tree.bean.TreeNode;
import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class Solution {

    /**
     * 由1加到target。
     * 不能使用乘除、if-else、switch-case、for 循环、while 循环，及条件判断语句等高级功能
     */
    public int mechanicalAccumulator(int target) {
        int[] result = {0};
        mechanicalAccumulator0(target,0,result);
        return result[0];
    }

    private boolean mechanicalAccumulator0(int target,int i,int [] result){
        result[0]+=i;
        return i == target || mechanicalAccumulator0(target,i+1,result);
    }

    /**
     * 二维字符串数组 grid，请判断是否能在 grid 中找到目标单词 target
     * 必须按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用
     * 例：
     * ["A","B","C","E"]
     * ["S","F","C","S"]
     * ["A","D","E","E"]
     * ABCCEDF存在  ABCCEDFB不存在
     */
    public boolean wordPuzzle(char[][] grid, String target) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (wordPuzzle0(grid,i,j,target,0)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean wordPuzzle0(char[][] grid, int i, int j, String target, int index) {
        if (index > target.length()-1){
            return true;
        }
        if (i < 0 || i > grid.length - 1 || j < 0 || j > grid[i].length - 1) {
            return false;
        }
        if (grid[i][j] != target.charAt(index)){
            return false;
        }
        char temp = grid[i][j];
        grid[i][j] = '0';
        if (!wordPuzzle0(grid,i+1,j,target,index+1)){
            if (!wordPuzzle0(grid,i-1,j,target,index+1)){
                if (!wordPuzzle0(grid,i,j+1,target,index+1)){
                    if (!wordPuzzle0(grid,i,j-1,target,index+1)){
                        grid[i][j] = temp;
                        return false;
                    }
                }
            }
        }
        grid[i][j] = temp;
        return true;
    }

    /**
     *  m x n 的二维矩阵 grid，自 grid[0][0] 开始 每次只能移动一格，
     *  不能移动到digit(i) + digit(j) > cnt  的格子中，返回可移动到的格子总数
     *  digit(x) 表示数字 x 的各数位之和，例：digit(12) = 3 、digit(2) = digit(20) = 2、digit(123) = 6
     *  例  m = 20, n = 5, cnt = 4   结果为  15
     *  m = 20, n = 5, cnt = 5   结果为  20
     *  m = 20, n = 5, cnt = 9   结果为  75
     * 0  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  10
     * 1  2  3  4  5  6  7  8  9  10 2  3  4  5  6  7  8  9  10 11
     * 2  3  4  5  6  7  8  9  10 11 3  4  5  6  7  8  9  10 11 12
     * 3  4  5  6  7  8  9  10 11 12 4  5  6  7  8  9  10 11 12 13
     * 4  5  6  7  8  9  10 11 12 13 5  6  7  8  9  10 11 12 13 14
     */
    public int wardrobeFinishing(int m, int n, int cnt) {
        boolean[][] visited= new boolean[m][n];
        return wardrobeFinishing0(0,0,m,n,cnt,visited);
    }

    private int wardrobeFinishing0(int i, int j, int m, int n, int cnt, boolean[][] visited) {
        if (i >= m || j >= n){
            return 0;
        }
        if (visited[i][j]){
            return 0;
        }
        if (digit(i)+digit(j) > cnt){
            return 0;
        }
        visited[i][j] = true;
        return 1+wardrobeFinishing0(i+1,j,m,n,cnt,visited)+wardrobeFinishing0(i,j+1,m,n,cnt,visited);
    }

    private int digit(int num){
        int result = 0;
        while (num != 0){
            result+=num%10;
            num/=10;
        }
        return result;
    }
    @Test
    public void testDigit(){
        System.out.println(digit(123));
    }
    /**
     * 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径
     *          1
     *     2          3
     *  3      1           4
     *      0      2            -4
     *  目标和为4的路径 1->2->1->0    1->3->4->-4
     */
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        LinkedList<List<Integer>> result = new LinkedList<>();
        LinkedList<Integer> integers = new LinkedList<>();
        pathTarget0(root,target,result,integers,0);
        return result;
    }

    private void pathTarget0(TreeNode root, int target, LinkedList<List<Integer>> result, LinkedList<Integer> integers,int cnt) {
        if (root == null){
            return;
        }
        integers.add(root.val);
        if (root.val+cnt == target && root.left == null && root.right == null){
            result.add(new LinkedList<>(integers));
        }else {
            pathTarget0(root.left,target,result,integers,cnt+root.val);
            pathTarget0(root.right,target,result,integers,cnt+root.val);
        }
        integers.removeLast();
    }

    /**
     * 找出字符串的全排列
     * 例：  abc
     * abc、acb、bac、bca、cab、cba
     */
    public String[] goodsOrder(String goods) {
        LinkedList<String> result = new LinkedList<>();
        goodsOrder0(goods.toCharArray(),0,result);
        return result.toArray(new String[0]);
    }

    private void goodsOrder0(char[] goods,int index,LinkedList<String> result){
        if (index == goods.length-1){
            result.add(new String(goods));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = index; i < goods.length; i++) {
            if (!set.add(goods[i])){
                continue;
            }
            char temp = goods[index];
            goods[index] = goods[i];
            goods[i] = temp;
            goodsOrder0(goods,index+1,result);
            goods[i] = goods[index];
            goods[index] = temp;
        }
    }
}
